package ca.jsbr.as2js_lib.utils.grid 
{
	import ca.jsbr.as2js_lib.utils.geom.Point;
	import flash.utils.Dictionary;
	/**
	 * ...
	 * @author jsbr [me@jsbr.ca]
	 */
	public class Astar
	{
		private const _MOVECOST:int = 10;
		private const _MAXCOUNT:int = 10;
		private var _tiles:Vector.<ITile>;
		private var _end:ITile;
		private var _start:ITile;
		private var _size:Point;
		private var _analyseDirection:Vector.<Point>;
		private var _cpt:Number;
		private var _reset:Vector.<ITile>;
		private var _lenTiles:Number;
		private var _closed:Dictionary;
		private var _open:Vector.<ITile>;
		private var _parent:Dictionary;
		private var _child:Dictionary;
		
		

		public function Astar(diagonal:Boolean=false,fastAlgo:Boolean=true) 
		{
			
			_closed = new Dictionary();
			if (!fastAlgo) {
				_parent = new Dictionary();
				_child = new Dictionary();
				_open = new Vector.<ITile>();
			}
			_analyseDirection = new Vector.<Point>();
			if (diagonal)
			{
				_analyseDirection.push(new Point(0, -1), new Point(0, 1),new Point(1, 0),new Point( -1, 0),new Point(1, 1), new Point( -1, -1),new Point(1, -1),new Point( -1, 1));
			}
			else
			{
				_analyseDirection.push(new Point(0, -1), new Point(0, 1),new Point(1, 0),new Point( -1, 0));
			}
		}
		
		public function setTiles(tiles:Vector.<ITile>,size:Point):void
		{
			_tiles = tiles;
			_size = size;
			_lenTiles = _size.x * _size.y;
		}
		
		
		public function findPath(start:ITile,end:ITile):Vector.<ITile>
		{

			
			_end = end;
			_start = start;
			
			_cpt = 0;
			var ret:Vector.<ITile> = findBreadCrumb(start, end);
			_closed = new Dictionary();
			if (_open) {
				_parent = new Dictionary();
				_child = new Dictionary();
				_open = new Vector.<ITile>();
			}
			return ret;
		}
		
		
		private function findBreadCrumb(start:ITile,end:ITile,del:int=-1):Vector.<ITile>
		{
			var ret:Vector.<ITile>;
			_cpt++;
			//var _breadCrumb:Vector.<ITile>=_breadCrumb
			var breadCrumb:Vector.<ITile>;
			_closed[start.position.x + start.position.y * _size.x] = true;
			if (_open)
			{
				if (del > -1)
					_open.slice(del, i);
				_open = _open.concat(analyseTile(start));
				breadCrumb = _open;
			}
			else
				breadCrumb = analyseTile(start);
			
			
			breadCrumb.sort(shortHeuristic);
			
			/*if (_cpt > _tiles.length)
				return null;*/
			var len:int = breadCrumb.length;
			
			for (var i:int = 0; i < len; i++)
			{
				var tile:ITile = breadCrumb[i];
				if (tile == end){
					ret = new Vector.<ITile>();
					_closed[breadCrumb[i]] = true;
					//break;
				}
				else if(!_closed[tile]) 
				{
					ret = findBreadCrumb(tile, end, i);
					if (_cpt > _tiles.length || ( _open && !_open.length))
						return null;
				}
				if (ret) {
					if(!_open || ret.length==0 || _parent[ret[ret.length-1]]==tile)
						ret.push(tile);
					break;
				}
			}
			return ret;
		}
		
		private function shortHeuristic(a:ITile,b:ITile):int
		{
			if (a.heuristic < b.heuristic)
				return -1;
			else if (a.heuristic > b.heuristic)
				return 1;
			else
				return 0;
		}
		
		private function analyseTile(tile:ITile):Vector.<ITile>
		{
			var ret:Vector.<ITile> = new Vector.<ITile>();
			var pos:Point = tile.position;
			var idTile:int;
			var x:int;
			var y:int;
			var len:int = _analyseDirection.length;
			for (var i:int = 0; i < len; i++)
			{
				var pt:Point = _analyseDirection[i];
				x = pos.x + pt.x
				if (x >= _size.x || x<0)
					continue;
				y = (pos.y + pt.y);
				if (y >= _size.y || y<0)
					continue;
				idTile = x + y * _size.x;
				if (_tiles[idTile].obstacle || _closed[x + y * _size.x]) {
					continue;
				}
				if(_parent)
					_parent[_tiles[idTile]] = tile;
				ret.push(calHeuristic(_tiles[idTile]));
			}
			return ret;
		}
		
		private function calHeuristic(tile:ITile,origine:ITile=null):ITile
		{
			/*if (!tile.heuristic)
			{*/
				var distance:Number = Math.abs(tile.position.x - _end.position.x) + Math.abs(tile.position.y - _end.position.y);
				//trace(tile.cost)
				tile.heuristic = tile.cost + distance;
			//}
			return tile;
		}

	}

}